package visualizer.client.algorithms.rbBst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

import java.util.ArrayList;
import java.util.List;

import static visualizer.client.algorithms.rbBst.RedBlackBSTUtils.*;
import static visualizer.client.utils.VisualizerUtils.DEFAULT_OUTER_COLOR;

/**
 * User: DDovzhenko
 * Date: 07.01.14
 * Time: 18:26
 */
public class RBBSTRemovingAlgorithm implements Algorithm {
    private static final String BLUE = "blue";
    private BinaryTree tree;
    private List<AlgoResult> results = new ArrayList<AlgoResult>();

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return results.get(step);
    }

    @Override
    public int getStepsCount(BinaryTree binaryTree, int inputValue) {
        results.clear();
        results.add(new AlgoResult(binaryTree.copyTree(true), "Удаление узла с ключом " + inputValue + ". По заданному ключу найдем узел для удаления." +
                " Далее удалим узел, как в обычном дереве поиска и, перекрашивая узлы и выполняя ротации, восстановим структуру красно-черного дерева."));
        tree = copyRBTree(binaryTree);
        BNode nodeToRemove = search(tree.getRoot(), inputValue);
        tree.refreshParents();
        if (nodeToRemove != null) {
            delete(nodeToRemove);
        }
        tree = copyRBTree(tree);
        results.add(new AlgoResult(tree, "Узел с ключом " + inputValue + (nodeToRemove != null ? " успешно удален" : " не существует и не может быть удален")));
        return results.size();
    }

    private BNode search(BNode node, Integer key) {
        if (node == null) {
            return null;
        }

        node.setOuterColor(BLUE);
        int cmp = key.compareTo(node.getValue());
        if (cmp < 0) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " < " + node.getValue() + ", обрабатываем левое поддерево"));
            node.setOuterColor(DEFAULT_OUTER_COLOR);
            return search(node.getLeftBNode(), key);
        } else if (cmp > 0) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " > " + node.getValue() + ", обрабатываем правое поддерево"));
            node.setOuterColor(DEFAULT_OUTER_COLOR);
            return search(node.getRightBNode(), key);
        } else {
            node.setOuterColor(BLUE);
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " = " + node.getValue() + ", узел найден. Приступим к удалению."));
            node.setOuterColor(DEFAULT_OUTER_COLOR);
            return node;
        }
    }

    private void delete(BNode p) {
        if (p.getLeftBNode() != null && p.getRightBNode() != null) {
            BNode smallest = p.getRightBNode();
            saveResultWithHighlightedNodes("У удаляемого узла есть оба потомка, поэтому найдем в его правом поддереве узел с наименьшим ключом", smallest);
            while (smallest.getLeftBNode() != null) {
                smallest = smallest.getLeftBNode();
                saveResultWithHighlightedNodes("У удаляемого узла есть оба потомка, поэтому найдем в его правом поддереве узел с наименьшим ключом", smallest);
            }
            saveResultWithHighlightedNodes("Узел с наименьшим ключом найден. Ставим его на место удаляемого узла и удалим найденный узел.", smallest);
            p.setValue(smallest.getValue());
            smallest.setValue(null);
            p = smallest;
        }
        BNode replacement = (p.getLeftBNode() != null ? p.getLeftBNode() : p.getRightBNode());
        if (replacement != null) {
            // Link replacement to parent
            replacement.setParent(p.getParent());

            // Fix replacement
            if (!isRed(p)) {
                saveResultWithHighlightedNodes("Удаляемый узел черный, необходимо восстановить свойства красно-черного дерева.", p);
                fixAfterDeletion(replacement);
            } else {
                saveResultWithHighlightedNodes("Удаляемый узел красный, свойства красно-черного дерева не нарушены.", p);
            }
            saveResultWithHighlightedNodes("Свойства красно-черного дерева восстановлены, удаляем ссылку на узел", p);
            if (p.getParent() == null) {
                tree.setRootNode(replacement);
            } else if (p == p.getParent().getLeftBNode()) {
                p.getParent().setLeftBNode(replacement);
            } else {
                p.getParent().setRightBNode(replacement);
            }

            // Null out links so they are OK to use by fixAfterDeletion.
            p.setLeftBNode(null);
            p.setRightBNode(null);
            p.setParent(null);
        } else if (p.getParent() == null) { // return if we are the only node.
            results.add(new AlgoResult(tree.copyTree(true), "Узел является корнем дерева без потомков, удаляем его из дерева."));
            tree.setRootNode(null);
        } else { //  No children. Use self as phantom replacement and unlink.
            saveResultWithHighlightedNodes("Удаляемый узел не имеет потомков, удалим его и проверим цвет.", p);
            p.setValue(null);
            if (!isRed(p)) {
                saveResultWithHighlightedNodes("Удаляемый узел черный, необходимо восстановить свойства красно-черного дерева.", p);
                fixAfterDeletion(p);
            } else {
                saveResultWithHighlightedNodes("Удаляемый узел красный, свойства красно-черного дерева не нарушены.", p);
            }
            saveResultWithHighlightedNodes("Удаляем ссылку на узел.", p);
            if (p.getParent() != null) {
                if (p == p.getParent().getLeftBNode()) {
                    p.getParent().setLeftBNode(null);
                } else if (p == p.getParent().getRightBNode()) {
                    p.getParent().setRightBNode(null);
                }
                p.setParent(null);
            }
        }
    }

    private void fixAfterDeletion(BNode x) {
        while (x != tree.getRoot() && !isRed(x)) {
            String nodeValue = x.getValue() == null ? "Удаляемый узел" : "Узел с ключом " + x.getValue();
            if (x == leftOf(parentOf(x))) {
                BNode sib = rightOf(parentOf(x));

                if (isRed(sib)) {
                    saveResultWithHighlightedNodes(nodeValue + " имеет красного брата. " +
                            "Делаем ротацию влево относительно отца, тогда брат станет родителем отца. Красим брата в черный цвет, а отца - в красный.", x, sib);
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    saveResultWithHighlightedNodes(nodeValue + " имеет красного брата. " +
                            "Делаем ротацию влево относительно отца, тогда брат станет родителем отца. Красим брата в черный цвет, а отца - в красный.", x, sib);
                    sib = rightOf(parentOf(x));
                }

                if (!isRed(leftOf(sib)) && !isRed(rightOf(sib))) {
                    saveResultWithHighlightedNodes(nodeValue + " имеет черного брата и двух черных племянников. " +
                            "Красим брата в красный цвет и переходим к рассмотрению родителя.", x, sib);
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    String endMessage;
                    if (!isRed(rightOf(sib))) {
                        saveResultWithHighlightedNodes(nodeValue + " имеет черного брата, у которого правый потомок - черный. " +
                                "Красим брата в красный цвет, а его левого потомка - в черный. " +
                                "Выполняем ротацию вправо относительно брата.", x, sib);
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        saveResultWithHighlightedNodes(nodeValue + " имеет черного брата, у которого правый потомок - черный. " +
                                "Красим брата в красный цвет, а его левого потомка - в черный. " +
                                "Выполняем ротацию вправо относительно брата.", x, sib);
                        sib = rightOf(parentOf(x));
                    }
                    endMessage = nodeValue + " имеет черного брата, у которого правый потомок - красный. " +
                            "Красим брата в цвет родителя, самого родителя и правого потомка брата - в черный. " +
                            "Выполняем ротацию влево относительно родителя.";
                    saveResultWithHighlightedNodes(endMessage, x, sib);
                    setColor(sib, parentOf(x).getInnerColor());
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    saveResultWithHighlightedNodes(endMessage, x, sib);
                    x = tree.getRoot();
                }
            } else { // symmetric
                BNode sib = leftOf(parentOf(x));

                if (isRed(sib)) {
                    saveResultWithHighlightedNodes(nodeValue + " имеет красного брата. " +
                            "Делаем ротацию вправо относительно отца, тогда брат станет родителем отца. Красим брата в черный цвет, а отца - в красный.", x, sib);
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    saveResultWithHighlightedNodes(nodeValue + " имеет красного брата. " +
                            "Делаем ротацию вправо относительно отца, тогда брат станет родителем отца. Красим брата в черный цвет, а отца - в красный.", x, sib);
                    sib = leftOf(parentOf(x));
                }

                if (!isRed(rightOf(sib)) && !isRed(leftOf(sib))) {
                    saveResultWithHighlightedNodes(nodeValue + " имеет черного брата и двух черных племянников. " +
                            "Красим брата в красный цвет и переходим к рассмотрению родителя.", x, sib);
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    String endMessage;
                    if (!isRed(leftOf(sib))) {
                        saveResultWithHighlightedNodes(nodeValue + " имеет черного брата, у которого левый потомок - черный. " +
                                "Красим брата в красный цвет, а его правого потомка - в черный. " +
                                "Выполняем ротацию влево относительно брата.", x, sib);
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        saveResultWithHighlightedNodes(nodeValue + " имеет черного брата, у которого левый потомок - черный. " +
                                "Красим брата в красный цвет, а его правого потомка - в черный. " +
                                "Выполняем ротацию влево относительно брата.", x, sib);
                        sib = leftOf(parentOf(x));
                    }
                    endMessage = nodeValue + " имеет черного брата, у которого левый потомок - красный. " +
                            "Красим брата в цвет родителя, самого родителя и левого потомка брата - в черный. " +
                            "Выполняем ротацию вправо относительно родителя.";
                    saveResultWithHighlightedNodes(endMessage, x, sib);
                    setColor(sib, parentOf(x).getInnerColor());
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    saveResultWithHighlightedNodes(endMessage, x, sib);
                    x = tree.getRoot();
                }
            }
        }

        if (isRed(x) && x.getValue() != null) {
            saveResultWithHighlightedNodes("Узел с ключом " + x.getValue() + " красный, красим его в черный цвет.", x);
            setColor(x, BLACK);
        }
    }

    private BNode rightOf(BNode node) {
        return node == null ? null : node.getRightBNode();
    }

    private BNode leftOf(BNode node) {
        return node == null ? null : node.getLeftBNode();
    }

    private BNode parentOf(BNode x) {
        return x == null ? x : x.getParent();
    }

    private void setColor(BNode p, String c) {
        if (p != null)
            p.setInnerColor(c);
    }

    /**
     * From CLR
     */
    private void rotateLeft(BNode p) {
        if (p != null) {
            BNode r = p.getRightBNode();
            p.setRightBNode(r.getLeftBNode());
            if (r.getLeftBNode() != null)
                r.getLeftBNode().setParent(p);
            r.setParent(p.getParent());
            if (p.getParent() == null)
                tree.setRootNode(r);
            else if (p.getParent().getLeftBNode() == p)
                p.getParent().setLeftBNode(r);
            else
                p.getParent().setRightBNode(r);
            r.setLeftBNode(p);
            p.setParent(r);
        }
    }

    /**
     * From CLR
     */
    private void rotateRight(BNode p) {
        if (p != null) {
            BNode l = p.getLeftBNode();
            p.setLeftBNode(l.getRightBNode());
            if (l.getRightBNode() != null) l.getRightBNode().setParent(p);
            l.setParent(p.getParent());
            if (p.getParent() == null)
                tree.setRootNode(l);
            else if (p.getParent().getRightBNode() == p)
                p.getParent().setRightBNode(l);
            else p.getParent().setLeftBNode(l);
            l.setRightBNode(p);
            p.setParent(l);
        }
    }

    private void saveResultWithHighlightedNodes(String text, BNode ... nodes) {
        for (BNode node : nodes) {
            node.setOuterColor(BLUE);
        }
        results.add(new AlgoResult(tree.copyTree(true), text));
        for (BNode node : nodes) {
            node.setOuterColor(DEFAULT_OUTER_COLOR);
        }
    }
}
